The present invention relates generally to mechanisms and methods for routing data packets between nodes within a network. More specifically, the present invention relates to methods and apparatus for routing data packets from a data queue through a protocol stack.
FIG. 1 is a diagrammatic representation of a conventional network configuration 100. As shown, data packets 104 are held within a plurality of data queues 102. For example, data packets 104a, 104b, and 104c are held within a first data queue, data packet 104d is held within a second data queue, data packet 104e is held within a third data queue, etc.
As shown, there are various types of data that go to the different data queues 102. For example, internet protocol (IP) data 10 goes to a first data queue and a second data queue; packet assembler disassembler (PAD) data 12 goes to another data queue; qualified logical link control (QLLC) data 14 goes to yet another data queue; and data link switching (DLSW) data 16 goes to yet another data queue.
The network configuration 100 also includes a plurality of diverse protocol stacks through which the data or data packets will be transmitted, and each protocol stack has one or more associated protocol levels (also referred to as protocol layers or contexts). In other words, each data packet is associated with one of the protocol stacks and will eventually be sent through the associated protocol stack. For example, a data packet 104e will be transmitted through an associated protocol stack that includes a virtual circuit (VC) protocol layer 112b, an X.25 protocol layer 110, a link logic control (LLC2) protocol layer 108a, and a physical protocol layer 106 associated with a hardware device (not shown). The hardware device is coupled to other hardware devices (not shown) of other network nodes (not show), such as another router or end destination.
The term protocol is defined as any type of information format that is used to communicate between any independent entities, such as two network nodes.
Each data queue is associated with one or more protocols (herein referred to as a xe2x80x9cprotocol stackxe2x80x9d), and these particular associations depend on the requirements of the particular application being implemented. For example, Internet Protocol data packets are transmitted directly from a data queue to the physical layer 106. As shown, data packet 104g is associated with the physical protocol layer 106 and is sent from the data queue to the physical layer 106. Likewise, data packets 104a through 104c are also only associated with the physical protocol layer 106.
Data packets may travel through various protocols before reaching the physical layer 106. For example, data packet 104f is associated with the virtual circuit (VC) protocol layer 112a, the X.25 protocol layer 110, the LLC2 protocol layer 108a, and the physical protocol layer 106. Likewise data queue 104e is associated with the VC protocol layer 112b, the X.25 protocol layer 110, the LLC2 protocol layer 108a, and the physical protocol layer 106. By way of another example, data packet 104d is only associated with the LLC2 protocol layer 108e and the physical protocol layer 106.
The data queues represent any suitable queuing mechanism for holding data packets at a point above a plurality of protocol layers. For example, the data queues may simply hold the data pending transmission in the order received. In another example, the data queues may control the quality of service provided to data pending transmission by organizing data into a plurality of queues that each assert a claim of dynamic strength on an opportunity to send. The data queues may be associated or located on any suitable type of data transmission device, such as a router device. A router is defined loosely as meaning any network node for receiving and transmitting data packets from and to another network node.
Each of the protocol layers typically communicate with other similar protocol layers (herein referred to as xe2x80x9cpeer entitiesxe2x80x9d) within other network devices. For example, the X.25 protocol layer 110 may communicate with another network device, which communication is represented by a virtual communication bus 114. Actually, the X.25 protocol layer 100 communicates with another peer X.25 protocol layer through the LLC2 protocol layer 108a, the physical protocol layer 106, the peer physical protocol layer, and peer LLC2 protocol layer. Likewise, the LLC2 protocol layers 108a and 108b each communicate with a peer LLC2 protocol layer, which communications are represented by virtual communication lines 116a and 116b, respectively. Physical layer 106 is configured to communicate with other peer physical layers of other network hardware devices through communication line 118.
A protocol context communicates with a peer context on another network node by using its lower layer protocol context(s). The conversation commonly includes control information, as well as the user data that is carried on behalf of the context""s own overlying protocol context(s). The context control information is originated and terminated by the contexts, whereas the user data is sent from and received by the user(s) of the protocol context in the network node.
Both the user data and control data are commonly presented as user data to the underlying protocol context. A protocol context may be required to prohibit user data communication (e.g., it is congested) while remaining capable of exchanging control information. Thus, a protocol context may need to determine whether it""s underlying protocol context path is capable of sending control information while maintaining its own context congestion status of being unable to accept user data. Any user data already accepted and queued by a protocol context may be considered control information and may be sent while the context remains unable to accept additional user data.
Peer protocol layers from different network devices or nodes typically pass control information back and forth through its lower protocol context(s) or layers. For example, a first node""s LLC2 protocol context may transmit control data to a second node""s LLC2 protocol context to indicate that the second node LLC2 protocol context should cease packet transmission. Likewise, the first node""s LLC2 protocol context may transmit information that indicates that the second node""s LLC2 context may resume transmission. Since flow control information is generally time-sensitive, transmission of such flow control information should not be unduly delayed.
Data packets are typically sent to the next protocol layer of an associated protocol stack as soon as the data queue is ready to send and the next protocol layer is ready to accept the data packets. For example, data packet 104e is sent to VC protocol context 112b. The data packet is then sent to the next protocol layer as soon as the current protocol layer is able to send and/or the next protocol level is ready to accept. If the next protocol level (e.g., the X.25 protocol 110) is unable to accept the data packet, the data packet is held within a queue of the protocol context itself. For example, if the X.25 protocol context 110 is unable to accept data packets, data packets are held within a queue of VC protocol context 112b. In sum, data packets are held within each protocol queue until a next protocol context is able to accept them.
Although conventional data packet transmission approaches work well under certain conditions, these approaches have associated disadvantages. For example, since data packets are typically sent to the next protocol level as soon as the next level is able to accept data packets, so-called xe2x80x9ctime warpxe2x80x9d effects may occur. That is, when a particular protocol context transfers a data packet downstream to a next protocol context, the particular protocol context loses control of the data packet. Thus, if the particular protocol context subsequently receives a request from a peer protocol context of another network device to stop transmission, this request cannot be applied to data packets that are already resident within the next protocol context. In sum, from the requesting network device""s perspective, the particular protocol context appears to disregard the request to cease transmission since the data packets that were sent prior to the request may be received by the requesting network device after the request is made.
One solution to this problem of apparently disregarding requests is to limit the number of data packets that may be held within the underlying protocol contexts. However, this solution results in different problems. For example, the transmission hardware may be unnecessarily limited to using less than its full capacity for transmitting data packets.
Additionally, parallel processing at a particular protocol level becomes a problem when a particular protocol queue within the protocol layer reaches capacity because, for example, the next protocol layer is unable to accept packets. It then becomes difficult to efficiently execute parallel processes within the protocol layer with the filled protocol queue. For instance, when a particular protocol layer passes a data portion to a process that runs concurrently with the receipt of data packets by the particular protocol layer, it may be difficult to reinsert the parallel process"" results into the data stream when the protocol queues are overloaded.
One example of a parallel process is a compression routine. A portion of a data packet accepted by a particular protocol context is passed to a compression algorithm while other data packets are accepted, processed, and stored within the protocol context""s queue or sent to the next protocol context. In other words, the data portion is input into the compression algorithm and processed by the algorithm while other data packets are accepted into the protocol queue. The compression algorithm may not be able to output its results when the protocol queue is at or near capacity. Additionally, if traffic is heavy, the compression algorithm may not be able to output its results for a significantly long period of time.
In view of the foregoing, there is a need for improved data packet transmission mechanisms and techniques for efficiently controlling transmission of data packets from a network device""s data queues through one of a diverse set of protocol stacks.
Accordingly, the present invention provides apparatus and methods for controlling transmission of data or data packets from a data queue through an associated protocol stack. In general terms, the present invention provides systems and methods for determining whether the associated protocol stack is ready to accept data packets from the data queue.
In sum, each protocol layer within a particular protocol stack associated with a particular data queue has an associated congestion data structure. Each congestion data structure is configured to indicate whether its associated protocol layer is congested or able to accept and/or send data packets to the next protocol layer. Each associated data structure may be analyzed to determine congestion status prior to sending the data packet through its associated protocol stack.
In one embodiment of the invention, a method for transmitting a packet from a data queue through an associated protocol stack is disclosed. The protocol stack is associated with one or more linked data structures. Each data structure indicates whether an associated protocol context is congested and is associated with a next data structure. It is determined whether a current protocol context in the protocol stack is congested by reference to an associated current data structure. If it is determined that the current protocol context is congested, the packet is held within the data queue. If it is determined that the current protocol context is not congested, it is determined whether there is a next data structure. In one alternative embodiment, it is determined whether there is a next data structure by determining whether the current data structure points to a next data structure. If it is determined that there is not a next data structure, the packet is transmitted through the protocol stack. In an alternative embodiment, the current data structure is a last congested data structure.
In another alternative embodiment, it is further determined whether any protocol contexts in the protocol stack are congested by reference to their associated data structures and by sequentially checking the associated data structures from a top data structure to a bottom data structure. If it is determined that all protocol contexts in the protocol stack are not congested, the packet from the data queue is transmitted through the protocol stack. If it is determined that one of the protocol contexts in the protocol stack is congested, the packet is held within the data queue and checking other protocol contexts for congestion is discontinued.
In another aspect, if it is determined that one of the protocol contexts in the protocol stack is congested, a pointer to the congested protocol context is stored. In yet another aspect, an associated data structure of the congested protocol context is defined as the current data structure after storing the pointer to the congested protocol context. The method is then repeated for the newly defined current data structure.
In an alternative embodiment, a current data structure associated with a current protocol context in the protocol stack is disclosed. The current protocol context is implemented on an accepted data packet before the accepted data packet is sent to a next protocol context in the protocol stack. The data structure includes a congestion indicator that specifies whether the current protocol context is able to accept and send a current data packet to the next protocol context.
In yet another aspect of the invention, a method for generating or modifying linked data structures associated with protocol contexts in the protocol stack is disclosed. A current protocol context is implemented on an accepted data packet before the accepted data packet is sent to a next protocol context in the protocol stack. It is determined whether the current protocol context is able to accept and send the received data packet to the next protocol context, and a current data structure associated with the current protocol context is generated or modified such that a congestion indicator specifies whether the current protocol context is able to accept and send the accepted data packet to the next protocol context.
In a further aspect, a router is disclosed. The router includes a plurality of interfaces arranged to control data communication between the router and other network devices, a data queue arranged to hold one or more data packets, a protocol stack arranged to accept the data packets from the data queue and transmit the data packets to another network device, and a processing unit arranged to implement processes associated with the router. The processing unit is operable to transmit a data packet from a data queue through a protocol stack when it is determined that the protocol stack is uncongested.
In another embodiment of the invention, an operating system software for use by a processor in directing operation of a data transmission system utilizing a data queue and a protocol stack is disclosed. The operating system software includes at least one processor-readable medium and a program mechanism embedded in the at least one processor-readable medium for transmitting a data packet from the data queue through the protocol stack when it is determined that two or more protocol contexts within the protocol stack are not congested.
In another embodiment, a method for transmitting a packet from a top protocol context through the top protocol context""s underlying protocol stack is disclosed. The top protocol context is associated with one or more linked data structures, and each data structure indicates whether an associated protocol context is congested and is associated with a next data structure. It is determined whether a current protocol context in the protocol stack is congested by reference to an associated current data structure. If it is determined that the current protocol context is congested, the data is not formed to send through the associated protocol stack. If it is determined that the current protocol context is not congested, it is determined whether there is a next data structure to check for congestion. If it is determined that there is not a next data structure, the data is formed and transmitted through the associated protocol stack.
The present invention has many advantages. For example, the linked data structures and a particular data packet""s association with one of these data structure chains allow for efficient traffic management. That is, one or more protocol contexts of a particular data packet""s associated protocol stack may be quickly checked for congestion at anytime by analyzing the relevant data structures since the entire associated data structure chain for the protocol stack may be associated with the data packet via pointers, for example.
Additionally, a protocol context can readily reference the congestion data structures to determine if the linked data structures below the context are congested. Thus, the protocol context can determine if it can create and send control information when its underlying services are not congested while maintaining independent congestion information for the users of the context itself. The chain of congestion data structures facilitates the ability of each protocol context to determine the total congestion status of the subset of protocol contexts that underlie it.
Additionally, the more data structures that are checked within an associated data structure chain, the more likely it will be that the protocol stack is uncongested when the data packet is transmitted from the data queue through the protocol stack. Likewise, the amount of queuing at each individual protocol level as a result of congestion in the next protocol context level may be significantly reduced. However, savings in processing time may be achieved by checking only a few data structures within the chain. Data structures may be chosen to increase reliability or decrease processing time of congestion detection. For example, a data structure of a protocol layer that is frequently congested may be included within the check to decrease the likelihood of erroneous determinations that the protocol stack is uncongested. By way of another example, the last congested protocol layer may be efficiently checked at the beginning. Since the last congested protocol context layer is likely to still be congested, this feature allows an efficient check to determine whether it is still congested before other protocol layers are unnecessarily checked.